package daily.year2024.m10;

/**
 * 123.买卖股票的最佳时机III
 *
 * @author wjs 2024/10/28
 */
public class d28 {
    //错误解法
    class Solution1 {
        //解法：动态规划
        //在股票买卖的基础上再加上一个状态，表示目前买卖了多少次
        public int maxProfit(int[] prices) {
            int n = prices.length;
            if(n == 1) {
                return 0;
            }
            int[][][] dp = new int[n][2][3];
            dp[0][1][0] = -prices[0];
            dp[0][1][1] = -1000000;
            dp[0][1][2] = -1000000;
            dp[0][0][1] = -1000000;
            dp[0][0][2] = -1000000;
            for(int i=1;i < n;i++) {
                for(int j=1;j <= 2;j++) {
                    dp[i][0][j] = Math.max(dp[i-1][1][j-1] + prices[i],dp[i-1][0][j-1]);
                }
                dp[i][1][0] = Math.max(-prices[i],dp[i-1][1][0]);
                dp[i][1][1] = Math.max(dp[i-1][1][1],dp[i-1][0][1]-prices[i]);
                dp[i][1][2] = Math.max(dp[i-1][1][2],dp[i-1][0][2]-prices[i]);
            }
            return Math.max(dp[n-1][0][2],dp[n-1][0][1]);
        }
    }

    //正确解法：动态规划，四种状态转移
    class Solution2 {
        public int maxProfit(int[] prices) {
            int n = prices.length;
            int buy1 = -prices[0], sell1 = 0;
            int buy2 = -prices[0], sell2 = 0;
            for (int i = 1; i < n; ++i) {
                buy1 = Math.max(buy1, -prices[i]);
                sell1 = Math.max(sell1, buy1 + prices[i]);
                buy2 = Math.max(buy2, sell1 - prices[i]);
                sell2 = Math.max(sell2, buy2 + prices[i]);
            }
            return sell2;
        }
    }
}
